/*
Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.
*/

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1[0]=='0'||num2[0]=='0') return "0";
        int n = num1.size()+num2.size();
        vector<int> r(n,0);
        string s(n,'0');
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        for (int i = 0; i < num1.size(); i++)
            for (int j = 0; j < num2.size(); j++)
                r[i+j] += (num1[i]-'0')*(num2[j]-'0');
        int carryover = 0;
        for (int i = 0; i < n; i++) {
            r[i] += carryover;
            carryover = r[i] / 10;
            r[i] %= 10; s[i] += r[i];
        }
        if (s[n-1] == '0') s.resize(n-1); // get rid of last 0
        reverse(s.begin(), s.end());
        return s;
    }
};
